package demo.Day06;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/22-07-22-10:26
 * @Description：demo.Day06   数组排序:(冒泡排序、选择排序、插入排序)
 */
public class Array_Sort {
    public static void main(String[] args) {
        int[] arr = {3,7,2,4,9,1,5};
        //BubberSort(arr);    //冒泡排序
        //SelectSort(arr);    //选择排序
        InsertSort(arr);     //插入排序
    }

    /**
     * 将数组划分为2组，左边一组已排序，右边未排序
     * 默认第一个值是已排
     * 新值，从未排的当前值与已排所有值比较，找到适合的位置插入  合适的位置：当前值比左边的所有值小，直到更大为止
     * @param arr
     */
    public static void InsertSort(int[] arr) {
//        for (int i = 0; i < arr.length-1; i++) {
//            for (int j = i+1; j < arr.length; j++) {
//                if(arr[i] > arr[j]){
//                    int temp = arr[i];
//                    arr[i] = arr[j];
//                    arr[j] = temp;
//                }
//            }
        for (int i = 1; i < arr.length; i++) {
            int index=i, temp = arr[i];
            for (int j = i-1; j >= 0; j--) {
                if(temp<arr[j]){
                    arr[j+1] = arr[j];
                    index = j;
                }else{
                    break;
                }
            }
            arr[index] = temp;
            System.out.print("第"+ (i+1) +"轮排序后：");
            print(arr);
            System.out.println();
        }
    }

    /**
     * 每一次排序中，在待排序元素中找到最小值，放到第i号位置    i从0~n-1
     * @param arr
     */
    public static void SelectSort(int[] arr) {
        int index = 0,temp;
        for (int i = 0; i < arr.length - 1; i++) {
            index = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[index]){
                    index = j;
                }
            }
            temp = arr[i];              //将第i号位置替换成最小值
            arr[i] = arr[index];
            arr[index] = temp;
            System.out.print("第"+ (i+1) +"轮排序后：");
            print(arr);
            System.out.println();
        }
    }

    /**
     * 冒泡排序，
     *      如果前面的数比后面的大，则交换位置，一次for循环只排一个数字
     * @param arr
     */
    public static void BubberSort(int[] arr) {
        int temp,length = arr.length;
        for (int i = 0; i < length-1; i++) {     //控制排序次数 length-1次
            for (int j = 0; j < length-1-i; j++) {         //  每一轮的相邻2个值作比较，前面的数大于后边的，则交换
                if(arr[j]>arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }                                    // 每一轮排好的位置为 第length-1-i个位置
            System.out.print("第"+ (i+1) +"轮排序后：");
            print(arr);
            System.out.println();
        }
    }

    public static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"\t");
        }
    }
}
